package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/19 17:42
 */
public class NumDecodings_91 {

    public int numDecodings(String s) {
        int len = s.length();
        if (s.charAt(0) == '0') return 0;
        int[] dp = new int[len + 1];
        dp[0] = 1;
        for (int i = 0; i <= len; i++) {
            dp[i + 1] = s.charAt(i) == '0' ? 0 : dp[i];
            if (i > 0 && judge(s.substring(i - 1, i + 1)))
                dp[i + 1] += dp[i - 1];
        }
        return dp[len];
    }

    public int numDecodings2(String s) {
        final int length = s.length();
        if (length == 0) return 0;
        if (s.charAt(0) == '0') return 0;

        int[] dp = new int[length + 1];
        dp[0] = 1;

        for (int i = 0; i < length; i++) {
            dp[i + 1] = s.charAt(i) == '0' ? 0 : dp[i];
            if (i > 0 && (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6'))) {
                dp[i + 1] += dp[i - 1];
            }
        }

        return dp[length];
    }

    public boolean judge(String s) {
        return s.compareTo("10") >= 0 && s.compareTo("26") <= 0;
    }

    static class Solution {

        public int numDecodingsBetter(String s) {
            // 一定需要对零的情况进行特殊讨论
            if (s.charAt(0) == '0') return 0;
            int cur = 0, pre = 1;
            char[] array = s.toCharArray();
            for (int i = 1; i < s.length(); i++) {
                int temp = cur;
                if (array[i] == '0') {
                    if (array[i - 1] == '1' || array[i - 1] == '2') cur = pre;
                    else return 0;
                } else {
                    // 状态压缩后
                    if (array[i - 1] == '1' || (array[i - 1] == '2' && array[i] <= '6'))
                        // cur代表前一位的种类数，pre代表前两位的种类数
                        cur += pre;
                }
                pre = temp;
            }
            return cur;
        }
    }

}
